package com.lw.leetcode.dp.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * arr
 * 321. 拼接最大数
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/24 10:10
 */
public class MaxNumber {

    public static void main(String[] args) {
        MaxNumber test = new MaxNumber();

        // [9, 8, 6, 5, 3]
//        int[] nums1 = {3, 4, 6, 5};
//        int[] nums2 = {9, 1, 2, 5, 8, 3};
//        int k = 5;

        // [9, 8, 9]
//        int[] nums1 = {3, 9};
//        int[] nums2 = {8, 9};
//        int k = 3;

        // [6, 7, 6, 0, 4]
//        int[] nums1 = {6, 7};
//        int[] nums2 = {6, 0, 4};
//        int k = 5;

        // [8,8]
        int[] nums1 = {8, 1, 8, 8, 6};
        int[] nums2 = {4};
        int k = 2;

        int[] ints = test.maxNumber(nums1, nums2, k);

        System.out.println(Arrays.toString(ints));

    }

    private int[] values;

    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        values = new int[k];
        int a = nums1.length;
        int b = nums2.length;
        int[] nums = new int[k];
        for (int i = 0; i <= k; i++) {
            if (i <= a && k - i <= b) {
                int[] ints1 = find(nums1, i);
                int[] ints2 = find(nums2, k - i);
                merge(ints1, ints2, nums);
            }
        }
        return values;
    }

    private void merge(int[] nums1, int[] nums2, int[] nums) {
        Arrays.fill(nums, 0);
        int a = nums1.length;
        int b = nums2.length;
        int i = 0;
        int j = 0;
        int index = 0;
        while (i < a && j < b) {
            int t1 = i;
            int t2 = j;

            boolean flag = false;
            while (t1 < a && t2 < b) {
                if (nums1[t1] < nums2[t2]) {
                    nums[index++] = nums2[j++];
                    flag = true;
                    break;
                } else if (nums1[t1] > nums2[t2]) {
                    nums[index++] = nums1[i++];
                    flag = true;
                    break;
                } else {
                    t1++;
                    t2++;
                }
            }
            if (!flag) {
                if (t1 == a) {
                    nums[index++] = nums2[j++];
                } else {
                    nums[index++] = nums1[i++];
                }
            }
        }

        while (i < a) {
            nums[index++] = nums1[i++];
        }
        while (j < b) {
            nums[index++] = nums2[j++];
        }
        for (int i1 = 0; i1 < nums.length; i1++) {
            if (nums[i1] > values[i1]) {
                System.arraycopy(nums, 0, values, 0, nums.length);
                return;
            } else if (nums[i1] < values[i1]) {
                return;
            }
        }
    }

    private int[] find(int[] nums, int l) {
        int[] arr = new int[l];
        int length = nums.length;
        if (l == 0) {
            return arr;
        }
        int index = 1;
        arr[0] = nums[0];
        for (int i = 1; i < length; i++) {
            if (l - index == length - i) {
                for (; i < length; i++) {
                    arr[index++] = nums[i];
                }
                return arr;
            }
            int n = nums[i];
            if (index == 0) {
                arr[index++] = n;
            } else {
                if (n <= arr[index - 1]) {
                    if (index < l) {
                        arr[index++] = n;
                    }
                } else {
                    i--;
                    index--;
                }
            }
        }
        return arr;
    }

}
